package cn.leonis.leetcode;

import java.util.Arrays;

/**
 * @Author Tobi
 * @Date 2021-07-13 上午1:13
 * 查找第一个出现的位置和最后一个出现的位置
 */
public class FindFirstAndLastPositionInSortedArraySolution {

    public static void main(String[] args) {
        int[] nums = new int[]{5, 7, 7, 8, 8, 10};
        int target = 8;
        FindFirstAndLastPositionInSortedArraySolution solution = new FindFirstAndLastPositionInSortedArraySolution();
        int[] ints = solution.searchRange1(nums, target);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 存在边界问题，对于边界存在的值，会出现数组越界
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};

        if (nums.length <= 0) {
            return result;
        }

        if (nums.length > 0 && (target < nums[0] || nums[nums.length - 1] < target)) {
            return result;
        }else {
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] > target) {
                    right = mid - 1;
                }else if (nums[mid] < target) {
                    left = mid + 1;
                }else {
                    left = right = mid;
                    result[0] = mid;
                    result[1] = mid;
                    // return result;
                }
            }
            // 对于有left==right的判断
            int pl = left, pr = right;
            while (pl > 0 || pr < nums.length - 1) {
                if (nums[pl] == target && nums[pl--] < target) {
                    result[0] = pl;
                }
                if (nums[pr] == target) {
                    result[1] = pr;
                    if (pr < nums.length - 1) {
                        pr++;
                    }
                }
                if (nums[pl] < target && nums[pr] > target) {
                    return result;
                }
            }
        }

        return result;
    }

    public int[] searchRange1(int[] nums, int target) {
        int leftIndex = binarySearch(nums, target, true);
        int rightIndex = binarySearch(nums, target, false) - 1;
        if (leftIndex <= rightIndex && rightIndex < nums.length && nums[leftIndex] == target && nums[rightIndex] == target) {
            return new int[]{leftIndex, rightIndex};
        }
        return new int[]{-1, -1};
    }

    /**
     * 二分查找实现
     * @param nums
     * @param target
     * @param low
     * @return
     */
    public int binarySearch(int[] nums, int target, boolean low) {

        int left = 0, right = nums.length - 1;

        // 由于无法处理位于数组最后一个元素
        int ans = nums.length;

        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] > target || (low && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            }else {
                left = mid + 1;
            }
        }

        return ans;
    }
}
